import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LeetCode438 {
    public static void main1(String[] args) {
        System.out.println(findAnagrams("cbaebabacd", "abc"));
    }
    public static List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
//        int[] arr = new int[128];
        // for (int i = 0; i < pLen; i++) {
        //     arr[p.charAt(i)] = 1;
        // }
        int kinds = 0;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < sLen - pLen + 1; i++) {
            String str = s.substring(i, i + pLen);
            int[] arr = new int[128];
            for (int k = 0; k < pLen; k++) {
                arr[p.charAt(k)]++;
            }
            for (int j = 0; j < pLen; j++) {
                char ch = str.charAt(j);
                if (arr[ch] != 0) {
                    arr[ch]--;
                } else {
                    break;
                }
            }
            if (isAllZero(arr)) {
                list.add(i);
            }
        }
        return list;
    }

    public static boolean isAllZero(int[] arr) {
        for (int i : arr) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> findAnagrams2(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        List<Integer> list = new LinkedList<>();
        int[] pArr = new int[128];
        for (int i = 0; i < pLen; i++) {
            char ch = p.charAt(i);
            pArr[ch]++;
        }
        int left = 0;
        int right = pLen;
        if (pLen > sLen) {
            return list;
        }
        int[] strArr = new int[128];
        for (int i = left; i < right - 1; i++) {
            char ch = s.charAt(i);
            strArr[ch]++;
        }
        while (right <= sLen) {
            strArr[s.charAt(right - 1)]++;
            if (isAangram(strArr, pArr)) {
                list.add(left);
            }
            strArr[s.charAt(left)]--;
            right++;
            left++;

        }
        return list;
    }

    public boolean isAangram(int[] strArr, int[] pArr) {
        for (int i = 0; i < 128; i++) {
            if (strArr[i] != pArr[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(findAnagrams3("cbaebabacd", "abc"));
    }

    public static List<Integer> findAnagrams3(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        int[] arr = new int[128];
        for (int i = 0; i < pLen; i++) {
            char ch = p.charAt(i);
            arr[ch]++;
        }
        int[] arr2 = new int[128];
        int count = 0;//记录有效字符
        List<Integer> list = new LinkedList<>();
        for (int left = 0, right = 0; right < sLen; right++) {
            char ch = s.charAt(right);
            arr2[ch]++;
            if (arr2[ch] <= arr[ch]) {
                count++;
            }
//            if (count == pLen) {
//                list.add(left);
//            }
            if (right - left == pLen) {
                if (arr2[s.charAt(left)] <= arr[s.charAt(left)]) {
                    count--;
//                    arr2[s.charAt(left)]--;
                }
                arr2[s.charAt(left)]--;
                left++;
            }
            if (count == pLen) {
                list.add(left);
            }
        }
        return list;
    }
}
